class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
    

def reverseList(head: ListNode) -> ListNode:
    # 判断链表为空时的情况
    if head is None: return head

    # 提取数字
    arr = []
    while head:
        arr.append(head.val)
        head = head.next
    
    # 翻转链表
    head = ListNode(arr.pop())
    p = head
    while arr:
        p.next = ListNode(arr.pop())
        p = p.next
    
    return head


# 双指针法
def reverseList(head: ListNode) -> ListNode:
    pre = None
    cur = head
    while cur:
        # tmp = cur.next
        # cur.next = pre
        # pre = cur
        # cur = tmp
        cur.next, pre, cur = pre, cur, cur.next
    return pre


if __name__ == "__main__":
    # 打印链表
    def printList(head: ListNode) -> None:
        while head:
            print(head.val, end=" -> ")
            head = head.next
        print(None)
    
    n = ListNode(1)
    p = n
    for i in range(2, 6):
        p.next = ListNode(i)
        p = p.next
    printList(n)

    n = reverseList(n)
    printList(n)
    
    print("Done!")